package dp;

import java.util.ArrayList;
import java.util.List;

public class P85 {
    public int maximalRectangle(char[][] matrix) {
        int rowLen = matrix.length;
        if (rowLen == 0) {
            return 0;
        }
        int colLen = matrix[0].length;
        int[][] dp = new int[rowLen + 1][colLen + 1];
        //遍历赋值
        int maxArea = 0;
        for (int r = 1; r <= rowLen; r++) {
            for (int c = 1; c <= colLen; c++) {
                char ch = matrix[r - 1][c - 1];
                if (ch == '0') {//当前位置为0
                    dp[r][c] = 0;
                } else if (ch == '1') {//当前位置为1
                    dp[r][c] = dp[r][c - 1] + 1;
                    List<Integer> list = new ArrayList<>();
                    int nr = r - 1;
                    while (nr > 0 && dp[nr][c] != 0) {
                        list.add(dp[nr][c]);
                        nr--;
                    }
                    int min = dp[r][c];
                    for (int i = 0; i < list.size(); i++) {
                        min = Math.min(min, list.get(i));
                        maxArea = Math.max(maxArea, (i + 2) * min);
                    }
                }
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {

    }
}
